//class Solution {
//public:
//     bool vis[101][101] = {{0}};
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    int m, n;
//    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
//        m = maze.size(), n = maze[0].size();
//        int ret = 0;
//        queue<pair<int, int>> q;
//        q.push({ entrance[0], entrance[1] });
//        vis[entrance[0]][entrance[1]] = true;
//        while (q.size())
//        {
//            ret++;
//            for (int levelsize = q.size(); levelsize > 0; levelsize--)
//            {
//                auto [a, b] = q.front();
//                q.pop();
//                for (int k = 0; k < 4; k++)
//                {
//                    int x = a + dx[k], y = b + dy[k];
//                    if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !vis[x][y])
//                    {
//                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1)
//                            return ret;
//                        q.push({ x, y });
//                        vis[x][y] = true;
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};




//class Solution {
//public:
//    char rpchar[4] = { 'A', 'C', 'G', 'T' };
//    int minMutation(string startGene, string endGene, vector<string>& bank) {
//        unordered_set<string> hash(bank.begin(), bank.end());
//        unordered_set<string> vis;
//        if (startGene == endGene) return 0;
//        if (hash.count(endGene) == 0) return -1;
//
//        queue<string> q;
//        q.push(startGene);
//        vis.insert(startGene);
//        int ret = 0, n = startGene.size();
//        while (q.size())
//        {
//            ret++;
//            int sz = q.size();
//            while (sz--)
//            {
//                string t = q.front();
//                q.pop();
//
//                for (int i = 0; i < 8; i++)
//                {
//                    string tmp = t;
//                    for (int j = 0; j < 4; j++)
//                    {
//                        tmp[i] = rpchar[j];
//                        if (hash.count(tmp) && !vis.count(tmp))
//                        {
//                            if (tmp == endGene)
//                                return ret;
//                            q.push(tmp);
//                            vis.insert(tmp);
//                        }
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};




class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(), wordList.end());
        if (beginWord == endWord) return 1;
        if (hash.count(endWord) == 0) return 0;
        unordered_set<string> vis;

        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);
        int ret = 1;
        while (q.size())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                string t = q.front();
                q.pop();
                for (int i = 0; i < t.size(); i++)
                {
                    string tmp = t;
                    for (int j = 0; j < 26; j++)
                    {
                        tmp[i] = j + 'a';
                        if (hash.count(tmp) && !vis.count(tmp))
                        {
                            if (tmp == endWord)
                                return ret;
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};